//
// Created by 1 on 2021-06-02.
//
#include <iostream>
using namespace std;

const int MaxSize = 100;
template <class DataType>
class SeqList {
public:
    SeqList() { length = 0; };		// 无参构造函数
    SeqList(DataType a[], int n);	//有参构造函数
    ~SeqList() {};					// 析构函数
    int Length() { return length; };	// 获取线性表当前长度
    DataType Get(int i);			// 根据索引返回元素的值
    int Locate(DataType x);			// 根据值定位元素所在位置索引
    void Insert(int i, DataType x);	// 在某个位置插入元素
    DataType Delete(int i);			// 删除某个位置的元素
    void printList();				// 遍历
private:
    DataType data[MaxSize];			// 顺序表使用数组实现
    int length;						// 存储顺序表的长度
};

template <class DataType>
SeqList<DataType>::SeqList(DataType a[], int n) {
    if (n > MaxSize) throw "参数错误";
    for (int i = 0; i < n; i++)
    {
        data[i] = a[i];
    }
    length = n;
}

template <class DataType>
int SeqList<DataType>::Locate(DataType a) {
    for (int i = 0; i < length; i++)
    {
        if (data[i] == a)
        {
            return i + 1;
        }
    }
    return 0;
}

template <class DataType>
DataType SeqList<DataType>::Get(int i) {
    if (i < 1 || i > length) throw "参数错误";
    return data[i - 1];
}

template <class DataType>
void SeqList<DataType>::Insert(int i, DataType x) {
    if (length >= MaxSize) throw "OverFlow";
    if (i<1 || i>length + 1) throw "insert location error";
    for (int j = length; j >= i; j--)
    {
        data[j] = data[j - 1];
    }
    data[i - 1] = x;
    length++;
}

template <class DataType>
DataType SeqList<DataType>::Delete(int i) {
    DataType x;
    if (length == 0) throw "Underflow";
    if (i<1 || i>length) throw "Location error";
    x = data[i - 1];
    for (int j = i; j <length; j++)
    {
        data[j-1] = data[j];
    }
    length--;
    return x;
}

template <class DataType>
void SeqList<DataType>::printList() {
    for (int i = 0; i < length; i++)
    {
        cout << data[i] << endl;
    }
}


int main() {
    SeqList<int> q;
    q.Insert(1, 5);
    q.Insert(2, 3);
    q.Insert(3, 1);
    q.Insert(4, 7);
    q.printList();
    cout << q.Length()<<endl;
    q.Insert(2, 9);
    q.printList();
    cout<<q.Get(2) << endl;
    q.Delete(4);
    q.printList();
    return 0;
}
